package backtrackStudy;


import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

public class Permute2 {

    private static List<List<Integer>> ans = new LinkedList<>();

    /**
     * 给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有不重复的全排列。
     * 总结：包含重复数字，只要保证重复数字的顺序是一样的即可。
     * @param args
     */
    public static void main(String[] args) {

    }

    public static List<List<Integer>> permuteUnique(int[] nums){
        StringBuilder sb = new StringBuilder();

        //处理传入的值
        Arrays.sort(nums);
        //存放路径
        LinkedList<Integer> trace = new LinkedList<>();
        //标记已经遍历过的元素
        boolean[] visited = new boolean[nums.length];
        //初始化标记数组
        Arrays.fill(visited, false);
        //回溯求结果
        backtrace(nums, visited, trace);
        //返回结果
        return ans;
    }

    //首先，确定返回值和参数
    public static void backtrace(int[] nums, boolean[] visited, LinkedList<Integer> trace){
        //确定出口
        if (trace.size() == nums.length){
            ans.add(new LinkedList<>(trace));
            return;
        }
        //循环
        for (int i = 0; i < nums.length; i++){
            //重构选择列表
            if (visited[i])
                continue;
            //保证重复数据出现的次序
            if (i>0 && nums[i]==nums[i - 1] && !visited[i - 1])
                continue;
            //选择
            trace.add(nums[i]);
            visited[i] = true;
            backtrace(nums, visited, trace);
            //取消选择
            visited[i] = false;
            trace.removeLast();
        }
    }
}
